1. Field of the Invention
The present invention relates to a data flow machine. More particularly, the present invention relates to a data flow machine in which an associative storage apparatus reads out, from data groups, data having a pattern identical to the pattern of data whose collating field is designated, and arithmetic processing of the data is performed.
2. Description of the Prior Art
FIG. 1 is a configuration diagram of a conventional data flow machine described for example in Iwanami Koza Microelectronics 8, VLSI Computer I (pp. 82-87, edited by T. Motooka, Oct. 10, 1984, Iwanami Shoten, Publishers). Referring to FIG. 1, the data flow machine comprises: an instruction packet forming portion for receiving an instruction, a type of the instruction and a destination node number outputted from a code memory 4 as well as two operands outputted from an operand memory 7 to form an instruction packet; an arithmetic processing unit for performing arithmetic processing according to the instruction upon receipt of the instruction packet; a result queue for temporarily storing a result packet outputted from the processing unit 2; a code memory 4 for storing a program to be executed and reading an instruction to be executed next, the type of the instruction and the destination node number according to the destination node number of the result packet; a switch 5 for determining the type of the instruction read out from the code memory 4 and selecting a path to the instruction packet forming portion 1; an associative storage portion 6 of an associative storage apparatus for providing an address of an operand memory 7 based on an activity number of the result packet (in a context for repeating the instruction or calling a procedure) and the destination node number; and the operand memory 7 of the associative storage apparatus for detecting a state in which two operands are received and ready for arithmetic processing.
Operation of the above described machine will be described.
When arithmetic processing is ready to be performed according to an instruction A, the instruction packet forming portion 1 receives the instruction outputted from the code memory 4 as well as the type of the instruction and the destination node number outputted therefrom and receives the activity number and one or two operands outputted from the operand memory 7 or the result queue 3, whereby an instruction packet A is formed and outputted to the arithmetic processing unit 2. Upon receipt of the instruction packet A, the arithmetic processing unit 2 performs arithmetic processing for the operands according to the instruction of the packet and outputs a result packet. The result packet is formed with the activity number of the instruction packet A and the destination node number being maintained. The result packet outputted from the arithmetic processing unit 2 is inputted to the result queue 3. The result queue 3 temporarily stores the result packet and outputs the destination node number of the result packet to the code memory 4. Upon receipt of the destination node number, the code memory 4 reads out, from this destination node number, the stored instruction, the type of the instruction and the destination node number (i.e., an instruction B). The instruction B is outputted to the switch 5 and the instruction packet forming portion 1. Upon receipt of the instruction B, the switch 5 examines the type of the instruction indicating whether the instruction is a 1-input instruction or a 2-input instruction and then, the switch 5 outputs the result to the result queue 3. If the type of the instruction is the 1-input instruction, the switch 5 connects the result queue 3 with the instruction packet forming portion 1. If it is the 2-input instruction, the switch 5 connects the operand memory 7 with the instruction packet forming portion 1.
Upon receipt of the type of the instruction from the switch 5, the result queue 3 outputs the result packet to the switch 5 if the type of the instruction indicates the 1-input instruction. At this time, the path from the result queue 3 to the instruction packet forming portion 1 is already set by the switching of the switch 5 and accordingly the result packet outputted from the result queue 3 is transmitted to the input packet forming portion 1 as a fired packet so that an instruction packet is formed by the thus transmitted packet as well as the instruction, the type of the instruction and the destination node number already outputted from the code memory 4.
If the type of the instruction from the switch 5 indicates the 2-input instruction, the result queue 3 outputs the result packet to the associative storage portion 6. The associative storage portion 6 hashes the activity number and the destination node number from the result queue 3. It associates the hashed numbers with an address in a queuing area for firing and outputs the address, as an address of the operand memory 7, together with the result packet.
The operand memory 7 receives the address and the result packet outputted from the associative storage portion 6 and reads out a content of the operand memory 7 corresponding to the address. If the other operand out of the two operands does not arrive, the result packet is stored in the address outputted from the associative storage portion 6 in the operand memory 7, so that a state waiting for the operand is set. On the other hand, if the other operand is already stored, the result packet outputted from the associative storage portion 6 is enabled to be fired and the result packet together with the already stored operand is outputted to the switch 5. At this time, since the type of the instruction indicates the 2-input instruction, the path from the operand memory 7 to the instruction packet forming portion 1 is already set by the switching of the switch 5 and accordingly the packet outputted from the operand memory 7 is transmitted to the instruction packet forming portion 1 so as to be the instruction packet.
Let us consider a case in which procedures according to a data flow graph of FIG. 2 are executed in the data flow machine in which the associative storage apparatus including the associative storage portion 6 and the operand memory 7 is used as a firing processing portion. In the following description, it is assumed that the operand memory 7 has a capacity for storing four operands.
Memory addresses of the operand memory 7, outputted from the associative storage portion 6 are four memory addresses for storing operands. The node numbers of the data flow graph of FIG. 2 are represented as the memory addresses shown in FIG. 3 and outputted to the associative storage portion 6. Thus, referring to FIG. 2, the first packet as a left input of the node number 3 and the second packet as a left input of the node number 7 indicate the same memory address in the operand memory 7 (i.e., the memory address "3"). If the second packet is stored in the operand memory 7 earlier than the first packet, the second packet waits for the third packet as a right input of the node number 7. The third packet is formed only after the operations of the node numbers 3, 5 and 6 are executed. However, since the first packet and the second packet collide, the first packet is not stored in the operand memory 7 and accordingly the operation of the node number 3 is not executed and as a result, execution of the data flow is stopped.
Thus, in the data flow machine using the associative storage apparatus having a smaller capacity than the number of nodes of the data flow to be executed, the same memory address is used for plural nodes for firing at the time of executing the data flow for a capacity larger than that of the operand memory. Consequently, there is involved a disadvantage that a collision might occur dependent on the order of the arrival of packets, causing stop of the execution of the data flow.